有限状态机问题编程实践
摘要：一般来说，实体的可能状态是有限的, 在满足一定的条件的情况下触发特定动作会发生实体的状态迁移。对于这类问题，我们一般称为FSM(Finite State Machine), 即有限状态机。本文分享一个有限状态机的java实现，以及使用DSL实现的通用化描述。
在日常开发工作中, 我们在建模时会经常遇到实体在多个状态间进行变迁的问题， 比如：
一个订单的状态可能是 “已下单” , “已支付”, “取消”, “完成” 等，并且在满足一定的条件的情况下触发特定动作会发生实体的状态迁移。一般来说，实体的可能状态是有限的, 对于这类问题，我们一般称为FSM(Finite State Machine), 即有限状态机。举个以前项目的例子：
某种设备通过GPRS连接到控制中心, 并且通过接受控制中心的控制指令来改变自身的运行状态,为了达到这个目的， 设备的底层系统提供了控制设备的API:
现在要求上层编写设备管理程序, 其状态图如下：
这是一个典型的状态机实现的问题, 设备拥有多个可能的状态, 并且在特定状态下接受正确的指令后可以迁移到指令的目标状态,直观的看，状态机是一个有向图，状态为端点，操作为边， 一个状态端点在特定操作的驱动下迁移到另一个状态端点。
一份快速的实现
我们用伪代码来描述如下:
define state = shutdown;
do function start();
set state = started;
done;
同时,一个完整的状态变迁图告诉我们如下事实:
一个状态端点可以由哪些状态端点变迁而来
一个状态端点可以变迁到哪些状态端点而去
那么针对这个问题我们可以快速的给出如下的一份实现:
//获取接受到的命令类型
final EventTypeEnum eventType = event.eventType();
//获取接受到的命令内容
final byte[] cmd = event.getInstruction();
switch (eventType) {
//接收到设备启动指令
case BOOT:
switch (currentDeviceStatus) {
//当前状态为关闭状态, 允许启动
case STATUS_POWEROFF:
//获取设备底层API并调用
DeviceRuntime.getDevice().boot(cmd);
currentDeviceStatus =
DeviceStatus.STATUS_BOOTED;
return true;
default:
return false;
}
//接受到设备关闭指令
case POWEROFF:
switch (currentDeviceStatus) {
//当前设备状态为已配置, 允许执行
case STATUS_CONFIURED:
//当前设备状态为已启动, 允许执行
case STATUS_BOOTED:
//当前设备状态为已待机, 允许执行
case STATUS_STANDBY:
//当前设备状态为在网待机,允许执行
case STATUS_LINKED_STANDBY:
DeviceRuntime.getDevice().shutdown(cmd);
currentDeviceStatus =
DeviceStatus.STATUS_POWEROFF;
return true;
default:
return false;
}
//接收到设备激活指令
case ACTIVE:
//...
case CONFIGURE:
//...
case LINK:
//...
case OFFLINE:
//...
case STANDBY:
//...
default:
return false;
我们用2层的switch来约束特定源状态，特定操作，特定目标状态， 如果不考虑状态机的修改，这应该是一个不错的实现，正确，简洁，易读. 但是在应付变化这方面就显得比较无能为力, 原因在于，这个版本的实现缺少结构化的抽象，缺乏职责划分导致无法做到变化的隔离。
考虑一下, 如果我们新增加一个状态， 按照当前的实现, 我们需要做的事情是这样的：
了解新端点是那些边的目标端点
在外层switch中为每条指向新端点的边构造一个switch分支，在内层switch中为每
个源端点构建一个状态变迁实现
了解新增端点是那些原有端点的源
在外层switch中为每条指向原有端点的边构造一个switch分支，在每个内层switch中为新增端点建立一个状态变迁实现
改进后的实现
很明显，正确的完成这件事情并不容易，试想如果一个状态机包含几十个状态，上百个动作，一次要新增或删除数个节点，改动和测试的复杂度将非常高。
下面我们来改进上面的实现, 前面讲过, 一个状态端点在特定操作的驱动下迁移到另一个状态端点, 这是状态机的唯一行为模式,是稳定的, 不稳定的是新增状态时的前置约束,指令的新增以及状态的变化, 所以从大体上我们需要把稳定的行为和不稳定的行为进行隔离和抽象。
首先, 我们再来对一次状态变迁进行分析：
一次状态迁移必然包含如下要素：
迁移的事件类型是什么? 比如启动, 激活, 关闭等
迁移的原状态时什么? 比如 启动类型的迁移, 其原状态必须是已关闭
迁移结束后的状态是什么? 比如 启动类型的迁移, 其目标状态时已启动
迁移指令如何执行
如果我们从这个角度来进行抽象, 我们需要一个操作模型来封闭起始状态和指令的执行,那么我们首先来定义一个设备的操作：
public interface DeviceOperation {
/**
* 返回此操作代表的类型
* @return 操作代表的类型
*/
public EventTypeEnum operationType();
/**
* 声明设备在什么状态下允许执行此操作
* @return 操作可执行的设备状态
*/
public Set<DeviceStatus> avaliableStatus();
/**
* 声明如果此指令操作成功, 设备应该处于的下一个状态
* @return 设备的新状态
*/
public DeviceStatus nextStatus();
/**
* 执行指令操作
* @param cmd 指令数据
*/
public void doOperation(final byte[] cmd);
}
一个操作(边)有它自己的类型, 有执行指令的实现，有目标端点和源端点。所有的要素都有了， 我们可以这样描述一个具体实现
操作X -> "操作X的类型为 operationType() , 在当前状态为 avaliableStatus()之一时允许执行指令操作doOperation(#cmd#)， 成功执行后设备状态更改为nextStatus()"
由于指令模型再执行指令时向上表现为一致的行为方式, 而底层设备为不同指令提供了不同的API, 因此在真正执行指令操作的地方, 我们也需要进行抽象和适配(下图仅列出部分操作)：
现在我们需要另外的一个模型来负责状态变迁的过程控制, 它需要足够的通用和稳定, 整个状态机的运行模式应该是这样：
//定义初始状态为shutdown
define state = shutdown;
//定义状态变迁的实例映射关系
define operations={启动:启动操作实例, 关闭:关闭操作实例...}
//接收到了消息
while receive x->{type,cmd}
//根据类型检索消息
deviceOperation = operations.get(x.type)
//强制状态检查
if deviceOperation.avaliableStatus() contains state; then
//执行指令
deviceOperation.doOperation(x.instruction)
//更新状态
state=deviceOperation.nextStatus()
endif
done
在能够按照我们想象的方式执行之前, 我们还需要一点灵活性, 将状态机的状态变迁图映射到操作模型中来, 也就是回答一个给定迁移动作的原状态和目标状态分别是什么以及如何执行的问题, 这一点可以通过配置的方式来完成, 比如:
<stateManagement>
<operation>
<eventType>boot</eventType>
<sourceStatus>
<value>powerOff</value>
</sourceStatus>
<targetStatus>started</targetStatus>
<actionExecutor>a.b.BootExecutor</actionExecutor>
</operation>
<operation>
<eventType>shutdown</eventType>
<sourceStatus>
<value>started</value>
<value>linked</value>
<value>standby</value>
<value>linkedstandby</value>
</sourceStatus>
<targetStatus>powerOff</targetStatus>
<actionExecutor>a.b.ShutDownExecutor</actionExecutor>
</operation>
....
</stateManagement>
通过解析这样的配置文件, 我们可以很容易的将操作类型与操作实例映射起来:
public class ConfiguredDeviceOperation implements DeviceOperation {
/** 操作类型 */
private final EventTypeEnum operationType;
/** 目标状态 */
private final DeviceStatus nextStatus;
private final DeviceStatus nextStatus;
/** 指令执行器 */
private final Executor executor;
/** 支持此操作的源状态集合 */
private final Set<DeviceStatus> avaliableStatus = new HashSet<DeviceStatus>();
/**
* 构造函数, 根据给定的配置服务对象构造一个设备操作对象
* @param operationType 操作类型
* @param nextStatus 下一个状态
* @param avaliableStatus 可执行操作的目标状态
* @param executor 执行器
*/
public ConfiguredDeviceOperation(final EventTypeEnum operationType, final DeviceStatus nextStatus, final
Set<DeviceStatus> avaliableStatus, final Executor executor) {
this.operationType = operationType;
this.nextStatus = nextStatus;
this.executor = executor;
this.avaliableStatus.addAll(avaliableStatus);
}
...
现在整个状态机每一条类型不同的边对应了一条配置，我们把易变的部分从状态迁移逻辑中抽离出来了，现在控制模型的代码只需要表达一个通用的执行流程，显著的增加了结构的稳定性：
//获取接受到的命令类型
final EventTypeEnum eventType = event.eventType();
//获取接受到的命令内容
final byte[] cmd = event.getInstruction();
//从加载的配置中获取设备操作实例
final DeviceOperation deviceOperation = CONFIG.get(eventType);
//判断当前状态是否可以执行操作
if(deviceOperation.avaliableStatus().contains(currentDeviceStatus)) {
deviceOperation.doOperation(cmd);
currentDeviceStatus = deviceOperation.nextStatus();
return true;
}
return false;
现在我们再回答要新增一个状态端点要做什么的问题:
在状态图中新增端点和边
对新指令添加新的指令执行器。
在配置中写出新增边的描述，对于已存在的边，在源状态列表中添加新的状态端点值。
归纳起来，我们需要新增指令执行器，增加和修改配置项。通过简单的改动，较大程度的消除了代码的更改，符合开闭原则，同时，对于配置项的修改，我们甚至可以更进一步，在后台中增加新的功能来辅助完成。从代码的复杂度上来看，消除了大量的分支判断，让代码更有层次，更加简洁了，读起来不再烧脑，从维护的角度看，减少代码的修改也就减少了出错的可能，从mock的角度看，我们抽象出了边的概念，使用mockito或你所熟悉的任意mock方式来修改其行为都是非常方便的。
通用化的描述-使用DSL
前面我们使用特定的java语法来实现了一个较为灵活的状态机，引入了一段xml配置文件来简化我们的实现, 但是对于描述像状态机这样有着显著领域特征的问题, 这种方式还是太程序化以及依赖编程技巧, 如果我们想要清晰的, 通用的表达我们所要解决的问题，或者想要提高开发效率，抽象构建模型，抽取公共的代码，减少重复的劳动，亦或想要灵活应对环境或平台的改变，脱离特定语言的捆绑， 那么我们可以考虑使用DSL来解决问题：
<stateManagement initial="powerOff">
<events>
<event id="deviceShutDown" type="shutdown" />
<event id="deviceBoot" type="boot" />
<event id="deviceActive" type="active" />
<event id="deviceStandBy" type="standby" />
...
</events>
<states>
<state name="powerOff">
<transition event="deviceBoot" target="started"/>
<state/>
<state name="started">
<transition event="deviceShutDown" target="powerOff"/>
<transition event="deviceStandBy" target="standby"/>
<state/>
<state name="standby">
<transition event="deviceShutDown" target="powerOff"/>
<transition event="deviceActive" target="started"/>
<state/>
...
<states/>
</stateManagement>
这里是一段状态机的外部DSL代码, 本质上就是一段XML, 我们抽取了这类问题的惯有模式,用声明的方式提供了事件类型, 状态以及此状态下可能的转换行为。这种DSL描述的控制结构可以很容易的与各种特定编程语言进行绑定,甚至可以定制化的进行代码生成。此外,从表述能力来看, 它明显会好过java实现的版本, 一个团队中的业务专家，开发，测试人员可以很容易的去阅读和理解，降低沟通和理解的成本。
结语
状态机是我们日常工作中非常常见的一种问题场景, 在这篇文章中我们对一个简单的例子进行分析并运用常见的工程手段来得出一个灵活的实现，文章中没有去谈论任何设计模式相关的东西, 而是着眼于更加本质的需求: 灵活, 简洁, 符合开闭原则 去不断的分析和改进, 最终获得一个满意的结果, 在此之外, 我们也尝试着使用外部DSL来抽取了状态机问题的惯有模式,区别于java语言版本的是, 这种方式更加注重通用化能力和信息交流的方便程度, 提供了更加可视化的，便携的解决方式。
给沪上的朋友们一个福利：），何涛&朱攀良心出品、唯品会、美团、德比软件、饿了么倾情奉献。
长按图片识别二维码或者点击阅读原文可以报名